Classic systems for performing division in data processing machines receive a dividend that is m digits wide and a divisor that is n digits wide, where n is smaller than m, and iteratively generate m-n quotient digits and a remainder that is n digits wide. The first quotient digit is generated by taking the first n digits of the dividend as a partial remainder. The divisor is subtracted from the partial remainder once each cycle until a negative result is reached. The number of subtractions of the divisor from the partial remainder necessary to generate a negative result less one is the first quotient digit. The value of the partial remainder prior to the last subtraction is saved for the generation of the next quotient digit.
The initial partial remainder for the next quotient digit takes the value of the prior partial remainder before the last subtraction concatenated with the next digit from the dividend. Again, the divisor is iteratively subtracted from the partial remainder until a negative result is reached. The process continues until m-n quotient digits are generated. The value of the partial remainder prior to the last subtraction during the generation of the last quotient digit is saved as the remainder.
As can be seen, the larger the quotient digit generated, the more cycles it takes to generate it.
The prior art is exemplified by decimal division on IBM/370-compatible computers. Operands for IBM/370-compatible decimal instructions consist of up to 16 bytes of data (except that one of the operands for multiply and divide cannot have more than 8 bytes) in the packed format. Each byte contains two decimal digits except for the rightmost byte, which contains a decimal digit on the left and a sign code on the right. Each decimal digit and sign code uses 4 bits. Table 1 illustrates how the binary digit and sign codes are interpreted. Operands with invalid digit or sign codes cause execution of the decimal instructions to be terminated.
TABLE 1 ______________________________________ Interpretation of Digit and Sign Codes Interpretation Code Digit Sign ______________________________________ 0000 0 Invalid 0001 1 Invalid 0010 2 Invalid 0011 3 Invalid 0100 4 Invalid 0101 5 Invalid 0110 6 Invalid 0111 7 Invalid 1000 8 Invalid 1001 9 Invalid 1010 Invalid Plus 1011 Invalid Minus 1100 Invalid Plus (preferred) 1101 Invalid Minus (preferred) 1110 Invalid Plus 1111 Invalid Plus ______________________________________
Decimal instructions on IBM/370-compatible computers have two operands. Both operands participate in the decimal operation, and the result replaces the first operand. For decimal divide, the first operand is the dividend, and the second operand is the divisor. The divisor cannot be longer than 8 bytes, and it must be shorter than the dividend.
The result of decimal division consists of a quotient placed leftmost in the first operand area and a remainder placed rightmost in the operand area. The remainder is the same length as the divisor, and the quotient length is the difference between the dividend length and the divisor length. The sign of the quotient is determined by the rules of algebra from the dividend and divisor signs. The sign of the remainder has the same value as the dividend sign. These rules hold even when the remainder or quotient is zero. Both the remainder and quotient receive preferred sign codes, but the dividend and divisor each may have any valid sign code. If the divisor is longer than 8 bytes or if the divisor is not shorter than the dividend or if the divisor is zero or if the quotient is too large to be represented in the area allotted for the quotient, then execution of the divide instruction is suppressed or terminated.
In IBM/370-compatible machines, the classic algorithm described above is implemented. Because of the large number of cycles it takes to iteratively determine each quotient digit, decimal division is a relatively long operation leading to bottlenecks in the execution of instructions. Accordingly, there is a need for improved divider algorithms and hardware that reduce the number of cycles required to perform decimal division.